/*
 * @lc app=leetcode.cn id=97 lang=cpp
 *
 * [97] 交错字符串
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        if (s1.length() > s2.length())
            s1.swap(s2);
        if (s1.length() == 0)
            return s3 == s2;
        if (s3.length() != s1.length() + s2.length())
            return false;

        vector<vector<bool>> dp(s1.length() + 1, vector<bool>(s2.length() + 1, 0));
        dp[0][0] = true;

        for (int i = 0; i <= s1.length(); i++)
        {
            for (int j = 0; j <= s2.length(); j++)
            {
                int p = i + j - 1;
                if (i > 0)
                {
                    dp[i][j] = dp[i][j] | (dp[i - 1][j] && (s1[i - 1] == s3[p]));
                }
                if (j > 0)
                {
                    dp[i][j] = dp[i][j] | (dp[i][j - 1] && (s2[j - 1] == s3[p]));
                }
            }
        }

        return dp[s1.length()][s2.length()];
    }
};
// @lc code=end
